Conventionally, Painter's algorithm is known as a method of performing a rasterizing process on a page printer. According to the Painter's algorithm, a mutual positional relation of graphics objects to be rendered is examined in advance, then the graphics object to be rendered in a backmost portion is first rendered to a frame store.
The Painter's algorithm has two problems. The first problem is that random access may occur to all the pixels in the frame store, and so a minute area of the frame store to be accessed cannot be identified in advance. For that reason, time for the rasterizing process is constrained by the product of the number of the pixels configuring all the graphics objects and the transfer time decided by physical transfer rate of a memory in which the frame store is placed. The second problem is that, in the case where the graphics objects are overlapping, the graphics object in the back is overpainted by the graphics object in the front, and so the time required to rasterize the overpainted area is wasted (called a problem of overwriting).
One of the methods for alleviating the two problems of the Painter's algorithm is banding. Banding is a method of dividing the frame store like bands and also dividing the graphics objects like bands in advance. In the case of banding, the memory to be accessed is limited to divided band-like areas (band areas). Therefore, it is possible to increase the probability of cache-hitting compared to the case of having a cache memory to access the entire frame store for instance. For this reason, the time for the rasterizing process is no longer constrained by the product of the number of the pixels configuring all the graphics objects and the transfer time decided by the physical transfer rate of the memory in which the frame store is placed. In the case of banding, however, the frame store is divided into several to several tens of pieces so that a cache-hit rate is not dramatically improved. The problem of overwriting cannot be solved either.
A method of causing no overwriting of the object which is the problem of the Painter's algorithm (called a second method) is also conceived. In one example of such a method, rendering of the objects is performed by using the following procedure. An image formed in the frame store is created in raster scan order. Coordinates of an intersection of each raster line and each object are acquired. For each pixel between the intersection coordinates, the object to be rendered is determined based on information on a level of the graphics objects included in the line (information indicating the mutual positional relation of the overlapping graphics objects in a direction of depth) and colors of the graphics objects. Rendering is performed between the intersections in a color corresponding to the object decided as a result of the determination. This is performed while updating the intersections with the graphics objects for each line (refer to Japanese Patent Laid-Open No. 2000-137825).
However, the above-mentioned conventional technique is not the one exploiting an image property of a high-resolution image. To be more specific, in the case of a high-resolution image, an arbitrary pixel in the image and a pixel in proximity thereto are highly likely to be of the same color value (this property is called spatial locality). This is because, as the objects included in the image has a certain expanse, the number of the pixels configuring one object increases when the resolution is high and the spatial locality becomes more obvious as a result thereof. For this reason, it is highly likely that an arbitrary pixel of an arbitrary line in an arbitrary frame store and a corresponding pixel in the line following it (that is, the pixel at the same position from an end of the line) have the same color value. The conventional technique performs an independent process for each individual line. For that reason, each individual line is generated independently even in the case where there are only a small number of pixels mutually corresponding and having differences in the color values or in the case where there is none. In other words, it is necessary to repeat the process even on the pixel which has the same color value as the pixel of the same position on the preceding line, which is waste of time.
In the case of the above-mentioned Painter's algorithm, the access to the frame store is random. The access is sequential in the second method. In the case where the access to the frame store is random, the pixels likely to be accessed are the entire frame store or the band areas according to the conventional technique. Therefore, an effect of a memory cache cannot be expected, or the effect is low. In the case of the second method, it is necessary to determine the color value transferred to the frame store from the mutual positional relation of the overlapping graphics objects in the direction of depth before the rendering. This determination process is under a heavy load and, as the arbitrary pixels of the frame store are accessed just once, the cache memory is substantially meaningless. For this reason, there is a problem that the cache memory cannot be effectively used.